package com.niuke;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName : demo2
 * @Author : kele
 * @Date: 2023/3/21 22:52
 * @Description :
 */
class point {

    int x;
    int y;
    point preve;

    public point(int x, int y, point preve) {
        this.x = x;
        this.y = y;
        this.preve = preve;
    }

}


public class labyrin {

    public static boolean idValid(int[][] matrix, int x, int y) {

        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {
            return false;
        } else if (matrix[x][y] == 1) {
            return false;
        } else {
            return true;
        }
    }

    public static List<point> solve(int[][] matrix, int startx, int starty, int endx, int endy) {

        ArrayList<point> list = new ArrayList<>();
        LinkedList<point> queue = new LinkedList<>();
        boolean[][] isVisist = new boolean[matrix.length][matrix[0].length];

        isVisist[startx][starty] = true;
        queue.add(new point(startx, starty, null));

        int[][] direct = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            point poll = queue.poll();


            if (poll.x == endx && poll.y == endy) {

                while (poll != null) {
                    list.add(poll);
                    poll = poll.preve;
                }

                Collections.reverse(list);
                break;
            }

            for (int[] dir : direct) {
                int x = poll.x + dir[0];
                int y = poll.y + dir[1];

                if (idValid(matrix, x, y) && !isVisist[x][y]) {

                    isVisist[x][y] = true;
                    queue.offer(new point(x, y, poll));

                }
            }
        }


        return list;

    }

    public static void main(String[] args) {


    }


}
